<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>Dictionary coder</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/Dictionary_coder"> <link href="./mw/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Dictionary_coder rootpage-Dictionary_coder skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Dictionary coder</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">
<style data-mw-deduplicate="TemplateStyles:r1251242444">
/* start https://en.wikipedia.org/ */
.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}
/* end https://en.wikipedia.org/ */
</style>
<p>A <b>dictionary coder</b>, also sometimes known as a <b>substitution coder</b>, is a class of <a href="Lossless_data_compression" class="mw-redirect" title="Lossless data compression">lossless data compression</a> algorithms which operate by searching for matches between the text to be compressed and a set of <a href="String_(computer_science)" title="String (computer science)">strings</a> contained in a <a href="Data_structure" title="Data structure">data structure</a> (called the 'dictionary') maintained by the encoder. When the encoder finds such a match, it substitutes a reference to the string's position in the data structure.
</p>
<div class="mw-heading mw-heading2"><h2 id="Methods_and_applications">Methods and applications</h2></div>
<p>Some dictionary coders use a 'static dictionary', one whose full set of strings is determined before coding begins and does not change during the coding process. This approach is most often used when the message or set of messages to be encoded is fixed and large; for instance, an <a href="Mobile_app" title="Mobile app">application</a> that stores the contents of a book in the limited storage space of a <a href="Personal_digital_assistant" title="Personal digital assistant">PDA</a> generally builds a static dictionary from a <a href="Concordance_(publishing)" title="Concordance (publishing)">concordance</a> of the text and then uses that dictionary to compress the verses. This scheme of using <a href="Huffman_coding" title="Huffman coding">Huffman coding</a> to represent indices into a concordance has been called "Huffword".<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>
</p><p>In a related and more general method, a dictionary is built from redundancy extracted from a data environment (various input streams) which dictionary is then used statically to compress a further input stream. For example, a dictionary is built from old English texts then is used to compress a book.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>
</p><p>More common are methods where the dictionary starts in some predetermined state but the contents change during the encoding process, based on the data that has already been encoded. Both the <a href="LZ77_(algorithm)" class="mw-redirect" title="LZ77 (algorithm)">LZ77</a> and <a href="LZ78" class="mw-redirect" title="LZ78">LZ78</a> algorithms work on this principle. In LZ77, a <a href="Circular_buffer" title="Circular buffer">circular buffer</a> called the "sliding window" holds the last <i>N</i> bytes of data processed. This window serves as the dictionary, effectively storing <i>every</i> substring that has appeared in the past <i>N</i> bytes as dictionary entries. Instead of a single index identifying a dictionary entry, two values are needed: the <i>length</i>, indicating the length of the matched text, and the <i>offset</i> (also called the <i>distance</i>), indicating that the match is found in the sliding window starting <i>offset</i> bytes before the current text.
</p><p>LZ78 uses a more explicit dictionary structure; at the beginning of the encoding process, the dictionary is empty. An index value of zero is used to represent the end of a string, so the first index of the dictionary is one. At each step of the encoding process, if there is no match, then the last matching index (or zero) and character are both added to the dictionary and output to the compressed stream. If there is a match, then the working index is updated to the matching index, and nothing is output.
</p><p><a href="LZW" class="mw-redirect" title="LZW">LZW</a> is similar to LZ78, but, the dictionary is initialized to all possible symbols. The typical implementation works with 8 bit symbols, so the dictionary "codes" for hex 00 to hex FF (decimal 255) are pre-defined. Dictionary entries would be added starting with code value hex 100. Unlike LZ78, if a match is not found (or if the end of data), then only the dictionary code is output. This creates a potential issue since the decoder output is one step behind the dictionary. Refer to <a href="LZW" class="mw-redirect" title="LZW">LZW</a> for how this is handled. Enhancements to LZW include handing symbol sizes other than 8 bits and having reserved codes to reset the dictionary and to indicate end of data.
</p><p><a href="Brotli" title="Brotli">Brotli</a> is an example of a commonly used coder that is initialised with a pre-defined dictionary, but later goes on to use more sophisticated content modelling. The Brotli dictionary consists largely of natural-language words and HTML and JavaScript fragments, based on an analysis of web traffic.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>
<style data-mw-deduplicate="TemplateStyles:r1239543626">
/* start https://en.wikipedia.org/ */
.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}
/* end https://en.wikipedia.org/ */
</style><div class="reflist">
<div class="mw-references-wrap"><ol class="references">
<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Ian H. Witten, Alistair Moffat, and Timothy C. Bell. <i>Managing Gigabytes</i>. New York: Van Nostrand Reinhold, 1994. <style data-mw-deduplicate="TemplateStyles:r1238218222">
/* start https://en.wikipedia.org/ */
.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}
/* end https://en.wikipedia.org/ */
</style><a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780442018634</bdi>.</span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">Rodney J. Smith. <i>Streaming Compression System Using Dynamic Connection Groups</i>, US patent 5,748,955, priority date 20 December 1993.</span>
</li>
<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://cran.r-project.org/web/packages/brotli/vignettes/brotli-2015-09-22.pdf">"Comparison of Brotli, Deflate, Zopfli, LZMA, LZHAM and Bzip2 Compression Algorithms"</a> <span class="cs1-format">(PDF)</span>. <i>cran.r-project.org</i>.</cite></span>
</li>
</ol></div></div>
<div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2></div>
<ul><li><a href="Grammar-based_code" title="Grammar-based code">Grammar-based code</a></li>
<li><a href="Entropy_encoding" class="mw-redirect" title="Entropy encoding">Entropy encoding</a></li></ul>
<div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">
/* start https://en.wikipedia.org/ */
.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}
/* end https://en.wikipedia.org/ */
</style><style data-mw-deduplicate="TemplateStyles:r1236075235">
/* start https://en.wikipedia.org/ */
.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}
/* end https://en.wikipedia.org/ */
</style></div><div role="navigation" class="navbox" aria-labelledby="Data_compression_methods241" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">
/* start https://en.wikipedia.org/ */
.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}
/* end https://en.wikipedia.org/ */
</style><div id="Data_compression_methods241" style="font-size:114%;margin:0 4em"><a href="Data_compression" title="Data compression">Data compression</a> methods</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Lossless_compression" title="Lossless compression">Lossless</a><br>type</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Entropy_coding" title="Entropy coding">Entropy</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Adaptive_coding" title="Adaptive coding">Adaptive coding</a></li>
<li><a href="Arithmetic_coding" title="Arithmetic coding">Arithmetic</a></li>
<li><a href="Asymmetric_numeral_systems" title="Asymmetric numeral systems">Asymmetric numeral systems</a></li>
<li><a href="Golomb_coding" title="Golomb coding">Golomb</a></li>
<li><a href="Huffman_coding" title="Huffman coding">Huffman</a>
<ul><li><a href="Adaptive_Huffman_coding" title="Adaptive Huffman coding">Adaptive</a></li>
<li><a href="Canonical_Huffman_code" title="Canonical Huffman code">Canonical</a></li>
<li><a href="Modified_Huffman_coding" title="Modified Huffman coding">Modified</a></li></ul></li>
<li><a href="Range_coding" title="Range coding">Range</a></li>
<li><a href="Shannon_coding" title="Shannon coding">Shannon</a></li>
<li><a href="Shannon%E2%80%93Fano_coding" title="Shannon–Fano coding">Shannon–Fano</a></li>
<li><a href="Shannon%E2%80%93Fano%E2%80%93Elias_coding" title="Shannon–Fano–Elias coding">Shannon–Fano–Elias</a></li>
<li><a href="Tunstall_coding" title="Tunstall coding">Tunstall</a></li>
<li><a href="Unary_coding" title="Unary coding">Unary</a></li>
<li><a href="Universal_code_(data_compression)" title="Universal code (data compression)">Universal</a>
<ul><li><a href="Exponential-Golomb_coding" title="Exponential-Golomb coding">Exp-Golomb</a></li>
<li><a href="Fibonacci_coding" title="Fibonacci coding">Fibonacci</a></li>
<li><a href="Elias_gamma_coding" title="Elias gamma coding">Gamma</a></li>
<li><a href="Levenshtein_coding" title="Levenshtein coding">Levenshtein</a></li></ul></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Byte-pair_encoding" title="Byte-pair encoding">Byte-pair encoding</a></li>
<li><a href="LZ77_and_LZ78" title="LZ77 and LZ78">Lempel–Ziv</a>
<ul><li><a href="842_(compression_algorithm)" title="842 (compression algorithm)">842</a></li>
<li><a href="LZ4_(compression_algorithm)" title="LZ4 (compression algorithm)">LZ4</a></li>
<li><a href="LZJB" class="mw-redirect" title="LZJB">LZJB</a></li>
<li><a href="Lempel%E2%80%93Ziv%E2%80%93Oberhumer" title="Lempel–Ziv–Oberhumer">LZO</a></li>
<li><a href="LZRW" title="LZRW">LZRW</a></li>
<li><a href="Lempel%E2%80%93Ziv%E2%80%93Storer%E2%80%93Szymanski" title="Lempel–Ziv–Storer–Szymanski">LZSS</a></li>
<li><a href="Lempel%E2%80%93Ziv%E2%80%93Welch" title="Lempel–Ziv–Welch">LZW</a></li>
<li><a href="LZWL" title="LZWL">LZWL</a></li>
<li><a href="Snappy_(compression)" title="Snappy (compression)">Snappy</a></li></ul></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Burrows%E2%80%93Wheeler_transform" title="Burrows–Wheeler transform">BWT</a></li>
<li><a href="Context_tree_weighting" title="Context tree weighting">CTW</a></li>
<li><a href="Context_mixing" title="Context mixing">CM</a></li>
<li><a href="Delta_encoding" title="Delta encoding">Delta</a>
<ul><li><a href="Incremental_encoding" title="Incremental encoding">Incremental</a></li></ul></li>
<li><a href="Dynamic_Markov_compression" title="Dynamic Markov compression">DMC</a></li>
<li><a href="Differential_pulse-code_modulation" title="Differential pulse-code modulation">DPCM</a></li>
<li><a href="Grammar-based_code" title="Grammar-based code">Grammar</a>
<ul><li><a href="Re-Pair" title="Re-Pair">Re-Pair</a></li>
<li><a href="Sequitur_algorithm" title="Sequitur algorithm">Sequitur</a></li></ul></li>
<li><a href="Discrete_cosine_transform" title="Discrete cosine transform">LDCT</a></li>
<li><a href="Move-to-front_transform" title="Move-to-front transform">MTF</a></li>
<li><a href="PAQ" title="PAQ">PAQ</a></li>
<li><a href="Prediction_by_partial_matching" title="Prediction by partial matching">PPM</a></li>
<li><a href="Run-length_encoding" title="Run-length encoding">RLE</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Hybrid</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li>LZ77 + Huffman
<ul><li><a href="Deflate" title="Deflate">Deflate</a></li>
<li><a href="LZX" title="LZX">LZX</a></li>
<li><a href="Lempel%E2%80%93Ziv%E2%80%93Stac" title="Lempel–Ziv–Stac">LZS</a></li></ul></li>
<li>LZ77 + ANS
<ul><li><a href="LZFSE" title="LZFSE">LZFSE</a></li></ul></li>
<li>LZ77 + Huffman + ANS
<ul><li><a href="Zstd" title="Zstd">Zstandard</a></li></ul></li>
<li>LZ77 + Huffman + context
<ul><li><a href="Brotli" title="Brotli">Brotli</a></li></ul></li>
<li>LZSS + Huffman
<ul><li><a href="LHA_(file_format)" title="LHA (file format)">LHA/LZH</a></li></ul></li>
<li>LZ77 + Range
<ul><li><a href="LZMA" title="LZMA">LZMA</a></li>
<li>LZHAM</li></ul></li>
<li>RLE + BWT + MTF + Huffman
<ul><li><a href="Bzip2" title="Bzip2">bzip2</a></li></ul></li></ul>
</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Lossy_compression" title="Lossy compression">Lossy</a><br>type</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Transform_coding" title="Transform coding">Transform</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Discrete_cosine_transform" title="Discrete cosine transform">Discrete cosine transform</a>
<ul><li><a href="Discrete_cosine_transform" title="Discrete cosine transform">DCT</a></li>
<li><a href="Modified_discrete_cosine_transform" title="Modified discrete cosine transform">MDCT</a></li></ul></li>
<li><a href="Discrete_sine_transform" title="Discrete sine transform">DST</a></li>
<li><a href="Fast_Fourier_transform" title="Fast Fourier transform">FFT</a></li>
<li><a href="Wavelet_transform" title="Wavelet transform">Wavelet</a>
<ul><li><a href="Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li>
<li><a href="Discrete_wavelet_transform" title="Discrete wavelet transform">DWT</a></li>
<li><a href="Set_partitioning_in_hierarchical_trees" title="Set partitioning in hierarchical trees">SPIHT</a></li></ul></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Predictive</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Differential_pulse-code_modulation" title="Differential pulse-code modulation">DPCM</a>
<ul><li><a href="Adaptive_differential_pulse-code_modulation" title="Adaptive differential pulse-code modulation">ADPCM</a></li></ul></li>
<li><a href="Linear_predictive_coding" title="Linear predictive coding">LPC</a>
<ul><li><a href="Algebraic_code-excited_linear_prediction" title="Algebraic code-excited linear prediction">ACELP</a></li>
<li><a href="Code-excited_linear_prediction" title="Code-excited linear prediction">CELP</a></li>
<li><a href="Log_area_ratio" title="Log area ratio">LAR</a></li>
<li><a href="Line_spectral_pairs" title="Line spectral pairs">LSP</a></li>
<li><a href="Warped_linear_predictive_coding" title="Warped linear predictive coding">WLPC</a></li></ul></li>
<li>Motion
<ul><li><a href="Motion_compensation" title="Motion compensation">Compensation</a></li>
<li><a href="Motion_estimation" title="Motion estimation">Estimation</a></li>
<li><a href="Motion_vector" class="mw-redirect" title="Motion vector">Vector</a></li></ul></li>
<li><a href="Psychoacoustics" title="Psychoacoustics">Psychoacoustic</a></li></ul>
</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data_compression#Audio" title="Data compression">Audio</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Bit_rate" title="Bit rate">Bit rate</a>
<ul><li><a href="Average_bitrate" title="Average bitrate">ABR</a></li>
<li><a href="Constant_bitrate" title="Constant bitrate">CBR</a></li>
<li><a href="Variable_bitrate" title="Variable bitrate">VBR</a></li></ul></li>
<li><a href="Companding" title="Companding">Companding</a></li>
<li><a href="Convolution" title="Convolution">Convolution</a></li>
<li><a href="Dynamic_range" title="Dynamic range">Dynamic range</a></li>
<li><a href="Latency_(audio)" title="Latency (audio)">Latency</a></li>
<li><a href="Nyquist%E2%80%93Shannon_sampling_theorem" title="Nyquist–Shannon sampling theorem">Nyquist–Shannon theorem</a></li>
<li><a href="Sampling_(signal_processing)" title="Sampling (signal processing)">Sampling</a></li>
<li><a href="Silence_compression" title="Silence compression">Silence compression</a></li>
<li><a href="Sound_quality" title="Sound quality">Sound quality</a></li>
<li><a href="Speech_coding" title="Speech coding">Speech coding</a></li>
<li><a href="Sub-band_coding" title="Sub-band coding">Sub-band coding</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Audio_codec" title="Audio codec">Codec</a><br>parts</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="A-law_algorithm" title="A-law algorithm">A-law</a></li>
<li><a href="%CE%9C-law_algorithm" title="Μ-law algorithm">μ-law</a></li>
<li><a href="Differential_pulse-code_modulation" title="Differential pulse-code modulation">DPCM</a>
<ul><li><a href="Adaptive_differential_pulse-code_modulation" title="Adaptive differential pulse-code modulation">ADPCM</a></li>
<li><a href="Delta_modulation" title="Delta modulation">DM</a></li></ul></li>
<li><a href="Fourier_transform" title="Fourier transform">FT</a>
<ul><li><a href="Fast_Fourier_transform" title="Fast Fourier transform">FFT</a></li></ul></li>
<li><a href="Linear_predictive_coding" title="Linear predictive coding">LPC</a>
<ul><li><a href="Algebraic_code-excited_linear_prediction" title="Algebraic code-excited linear prediction">ACELP</a></li>
<li><a href="Code-excited_linear_prediction" title="Code-excited linear prediction">CELP</a></li>
<li><a href="Log_area_ratio" title="Log area ratio">LAR</a></li>
<li><a href="Line_spectral_pairs" title="Line spectral pairs">LSP</a></li>
<li><a href="Warped_linear_predictive_coding" title="Warped linear predictive coding">WLPC</a></li></ul></li>
<li><a href="Modified_discrete_cosine_transform" title="Modified discrete cosine transform">MDCT</a></li>
<li><a href="Psychoacoustics" title="Psychoacoustics">Psychoacoustic model</a></li></ul>
</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Image_compression" title="Image compression">Image</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Chroma_subsampling" title="Chroma subsampling">Chroma subsampling</a></li>
<li><a href="Coding_tree_unit" title="Coding tree unit">Coding tree unit</a></li>
<li><a href="Color_space" title="Color space">Color space</a></li>
<li><a href="Compression_artifact" title="Compression artifact">Compression artifact</a></li>
<li><a href="Image_resolution" title="Image resolution">Image resolution</a></li>
<li><a href="Macroblock" title="Macroblock">Macroblock</a></li>
<li><a href="Pixel" title="Pixel">Pixel</a></li>
<li><a href="Peak_signal-to-noise_ratio" title="Peak signal-to-noise ratio">PSNR</a></li>
<li><a href="Quantization_(image_processing)" title="Quantization (image processing)">Quantization</a></li>
<li><a href="Standard_test_image" title="Standard test image">Standard test image</a></li>
<li><a href="Texture_compression" title="Texture compression">Texture compression</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Methods</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Chain_code" title="Chain code">Chain code</a></li>
<li><a href="Discrete_cosine_transform" title="Discrete cosine transform">DCT</a></li>
<li><a href="Deflate" title="Deflate">Deflate</a></li>
<li><a href="Fractal_compression" title="Fractal compression">Fractal</a></li>
<li><a href="Karhunen%E2%80%93Lo%C3%A8ve_theorem" class="mw-redirect" title="Karhunen–Loève theorem">KLT</a></li>
<li><a href="Pyramid_(image_processing)" title="Pyramid (image processing)">LP</a></li>
<li><a href="Run-length_encoding" title="Run-length encoding">RLE</a></li>
<li><a href="Wavelet_transform" title="Wavelet transform">Wavelet</a>
<ul><li><a href="Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li>
<li><a href="Discrete_wavelet_transform" title="Discrete wavelet transform">DWT</a></li>
<li><a href="Embedded_zerotrees_of_wavelet_transforms" title="Embedded zerotrees of wavelet transforms">EZW</a></li>
<li><a href="Set_partitioning_in_hierarchical_trees" title="Set partitioning in hierarchical trees">SPIHT</a></li></ul></li></ul>
</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data_compression#Video" title="Data compression">Video</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Bit_rate" title="Bit rate">Bit rate</a>
<ul><li><a href="Average_bitrate" title="Average bitrate">ABR</a></li>
<li><a href="Constant_bitrate" title="Constant bitrate">CBR</a></li>
<li><a href="Variable_bitrate" title="Variable bitrate">VBR</a></li></ul></li>
<li><a href="Display_resolution" title="Display resolution">Display resolution</a></li>
<li><a href="Film_frame" title="Film frame">Frame</a></li>
<li><a href="Frame_rate" title="Frame rate">Frame rate</a></li>
<li><a href="Video_compression_picture_types" title="Video compression picture types">Frame types</a></li>
<li><a href="Interlaced_video" title="Interlaced video">Interlace</a></li>
<li><a href="Video#Characteristics_of_video_streams" title="Video">Video characteristics</a></li>
<li><a href="Video_quality" title="Video quality">Video quality</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Video_codec" title="Video codec">Codec</a><br>parts</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Discrete_cosine_transform" title="Discrete cosine transform">DCT</a></li>
<li><a href="Differential_pulse-code_modulation" title="Differential pulse-code modulation">DPCM</a></li>
<li><a href="Deblocking_filter" title="Deblocking filter">Deblocking filter</a></li>
<li><a href="Lapped_transform" title="Lapped transform">Lapped transform</a></li>
<li>Motion
<ul><li><a href="Motion_compensation" title="Motion compensation">Compensation</a></li>
<li><a href="Motion_estimation" title="Motion estimation">Estimation</a></li>
<li><a href="Motion_vector" class="mw-redirect" title="Motion vector">Vector</a></li></ul></li>
<li><a href="Wavelet_transform" title="Wavelet transform">Wavelet</a>
<ul><li><a href="Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li>
<li><a href="Discrete_wavelet_transform" title="Discrete wavelet transform">DWT</a></li></ul></li></ul>
</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Information_theory" title="Information theory">Theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Compressed_data_structure" title="Compressed data structure">Compressed data structures</a>
<ul><li><a href="Compressed_suffix_array" title="Compressed suffix array">Compressed suffix array</a></li>
<li><a href="FM-index" title="FM-index">FM-index</a></li></ul></li>
<li><a href="Entropy_(information_theory)" title="Entropy (information theory)">Entropy</a></li>
<li><a href="Information_theory" title="Information theory">Information theory</a>
<ul><li><a href="Timeline_of_information_theory" title="Timeline of information theory">Timeline</a></li></ul></li>
<li><a href="Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li>
<li><a href="Prefix_code" title="Prefix code">Prefix code</a></li>
<li><a href="Quantization_(signal_processing)" title="Quantization (signal processing)">Quantization</a></li>
<li><a href="Rate%E2%80%93distortion_theory" title="Rate–distortion theory">Rate–distortion</a></li>
<li><a href="Redundancy_(information_theory)" title="Redundancy (information theory)">Redundancy</a></li>
<li><a href="Data_compression_symmetry" title="Data compression symmetry">Symmetry</a></li>
<li><a href="Smallest_grammar_problem" title="Smallest grammar problem">Smallest grammar problem</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Community</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Hutter_Prize" title="Hutter Prize">Hutter Prize</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">People</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Mark_Adler" title="Mark Adler">Mark Adler</a></li>
<li><a href="Phil_Katz" title="Phil Katz">Phil Katz</a></li></ul>
</div></td></tr></tbody></table></div></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2025-06-21" href="https://en.wikipedia.org/wiki/?title=Dictionary_coder&oldid=1296621088">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
</body></html>